1. Field of the Invention
The present invention relates to image analysis methods and systems for automatically identifying objects in a background by generating a description, which may be either a histogram or a co-occurrence matrix, of the gray level space of an image of the object and the background.
2. Description of the Related Art
Analyzing a representation of gray level space of an image has previously been proposed by D. Marr in an article entitled "Early Processing of Visual Information", Image Understanding, eds. S. Ullman and W. Richards, Ablex Publishing Company, 1984. The concept of entropy in information theory for signal processing was first proposed by Shannon in an article entitled "A Mathematical Theory of Communication" Bell System Technology J., Vol 27, July 1948, pp. 379-423. Shannon showed that the entropy function: ##EQU1## uniquely satisfies the following three properties:
(1) H(p.sub.1,p.sub.2, . . . p.sub.n) is a maximum for P.sub.k =1/n for k=1, . . . n;
(2) H(AB)=H(A)+HA(B), where A and B are two finite partitions and H.sub.A (B) is the conditional entropy of partition B given partition A;
(3) H(p.sub.1,p.sub.2, . . . p.sub.n,0)=H(p.sub.1,p.sub.2, . . . p.sub.n)
In addition, H.sub.max (1/n, . . . 1/n)=ln n.
The idea of using entropy to analyze a gray level histogram of an image was originally proposed by Pun in an article entitled "Entropic Thresholding, a New Approach", Comp. Graphics and Image Proc., Vol. 16, 1981, pp. 210-239. The entropy analysis of Pun was further refined by Kapur et al. in an article entitled "A New Method for Grey-Level Picture Thresholding Using the Entropy of the Histogram", Comp. Graphics and Image. Proc. 29, 1985, pp. 273-285. As shown by Pun and refined by Kapur, the concept of entropy can be extended to two dimensions if the gray level histogram of the image is used to define a probability distribution: EQU P.sub.s =f.sub.s /N for s=1, . . . , N.sub.gray ( 2)
where
fs=frequency of gray level s PA1 N=# pixels in image PA1 N.sub.gray =# gray levels
It follows that the entropy function of a histogram describing an image with a uniform gray level distribution is at a maximum. The more peaks in the distribution, the lower the entropy.
Pal and Pal, in an article entitled "Entropic Thresholding" Signal Processing, Vol 16, 1989, pp 97-108, recognized that a gray level histogram does not contain information regarding the spatial relationship between the gray levels and suggested the use of a two-dimensional data structure as an alternative to the gray level histogram. The structure suggested is a Haralick co-occurrence matrix as described by Haralick et al. in "Textural Features for Image Classification" IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-3, No. 6, 1973, pp. 610-621.
The techniques described above for analyzing the gray level space of an image compute a single entropic threshold and do not contemplate a system for recursively analyzing the gray level space of the image by automatically computing multiple entropic thresholds. Moreover, the above-discussed articles are not concerned with object validation and do not propose a driver for object comparison and validation.
In an article entitled "Automatic Multi-threshold Selection" Computer Vision Graphics and Image Processing Vol. 25, 1984, pp. 46-67, Wang and Haralick describe an attempt at multi-threshold selection using gray level distributions in local neighborhoods of each pixel in an image. This technique does not employ image entropy. Rather, it adaptively computes the local background of an object as an image is scanned by a priori selection of a gray level neighborhood.
Automated bacterial colony counting systems are commercially available for determining the number of visible bacteria in or on a culture medium such as a Petri dish. Examples include a Domino Image Analysis System made by Perceptive Instruments (Essex, England), a Seescan Imaging Plate Reader made by Seescan Imaging Limited (Cambridge, England), a Protos Colony Counter and Image 40-10 Analyzer, made by Analytical Measuring Systems (Cambridge, England), Bio-Foss Colony Counting System made by Foss Electric (York, England), an Artek 810 Image Analyzer made by Dynatech Laboratories, Inc. (Chantilly, Va.), an Optimas Image Analyzer made by Bio Scan (Edmonds, Wash.), a Video Densitometer II made by Biomed Instruments, Inc. (Fullerton, Calif.), and an Image-Pro Plus made by Media Cybernetics (Silver Spring, Md.). All of these instruments require the input of a single predetermined threshold per each image. None are capable of using image entropy to recursively compute multiple thresholds for object identification.
A semi-automated system for detection and quantification of microbial growth in sections of food has been described by Fernandes et al. in "Detection and Quantification of Microorganisms in Heterogeneous Foodstuffs by Image Analysis" Cabios Vol 4, No 2, 1988, pp 291-295. The system described in this article relies on manually examining the gray level histogram to identify a single threshold.
A number of patents have issued on colony counting systems, such as U.S. Pat. No. 4,637,053 to Schalkowsky, U.S. Pat. No. 3,811,036 to Perry, U.S. Pat. No. 3,736,432, and French Patent Application No. 2,602,074 to Segui et al. None of these patents discloses the concept of using image entropy to adaptively segment an image for colony enumeration and identification. "Adaptively segmenting" means thresholding the image with more than one threshold gray level.
Accordingly, it is an object of the present invention to provide methods and systems which use an entropically selected threshold gray level to search an image for automatic object identification.
It is also an object of the present invention to provide methods and systems which use entropically selected threshold gray levels to recursively search an image for automatic object identification.
It is further an object of the present invention to provide a method and a system for automatic object identification which can be used in colony counting, colony screening, identification of discrete features in carpets and identification of pigment elements embedded in a polymer.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.